package com.xieyong.leetcode;

public class Leetcode3405 {
    public static void main(String[] args) {
        Leetcode3405 leetcode3405 = new Leetcode3405();
        int n = 5581,m = 58624,k = 4766;
        int i = leetcode3405.countGoodArrays(n, m, k);
        System.out.println(i);
    }
    static final int MOD = (int)1e9 + 7;
    static final int MX = 100000;
    static long[] fact = new long[MX];
    static long[] invFact = new long[MX];

    static long qpow(long x, int n) {
        long res = 1;
        while (n > 0) {
            if ((n & 1) == 1) {
                res = res * x % MOD;
            }
            x = x * x % MOD;
            n >>= 1;
        }
        return res;
    }

    static {
        fact[0] = 1;
        for (int i = 1; i < MX; i++) {
            fact[i] = fact[i - 1] * i % MOD;
        }
        invFact[MX - 1] = qpow(fact[MX - 1], MOD - 2);
        for (int i = MX - 1; i > 0; i--) {
            invFact[i - 1] = invFact[i] * i % MOD;
        }
    }

    long comb(int n, int m) {
        return fact[n] * invFact[m] % MOD * invFact[n - m] % MOD;
    }

    public int countGoodArrays(int n, int m, int k) {
        return (int)(comb(n - 1, k) * m % MOD * qpow(m - 1, n - k - 1) % MOD);
    }


//          数字太大了存不下，而且时间比较慢
//    public int countGoodArrays(int n, int m, int k) {
////        对于第一项，总有m个选择可以选，不论后面的数字是什么
//        long res = m;
//        long resmod = (int)Math.pow(10, 9) + 7;
//        res = res % resmod;
////          对于剩下的 n - 1 个项，需要从中选出k个项，使其恰好满足arr[i] == arr[i - 1],且每个项都分别固定
////        那么就是组合数C(n-1，k)
//        long fenzi = 1;
//        for (int i = n - 1; i >= 2; i--) {
//            fenzi *= i % resmod;
//        }
//        long fenmu1 = 1;
//        for (int i = k; i >= 2; i--) {
//            fenmu1 *= i % resmod;
//        }
//        long fenmu2 = 1;
//        for (int i = n - 1 - k; i >= 2; i--) {
//            fenmu2 *= i % resmod;
//        }
//        long fenmu = (fenmu1 * fenmu2) % resmod;
//        long zuheshu = (fenzi / fenmu) % resmod;
//        res = (res * zuheshu) % resmod;
////          对于除了上面之外的 n - 1 - k 个项， 每个项总是满足arr[i] != arr[i - 1],即与k个项都分别不同，共有 m - 1 种选择
//        long resOther = 1;
//        for (int i = n - 1 - k; i >= 1; i--) {
//            resOther *= (m - 1) % resmod;
//        }
//        res = res * resOther;
//        return (int)(res % resmod);
//    }
}
